package leetcode;

/**
 * @author: feiwang_6
 * @create: 2020/7/16 16:08
 * @description: 寻找数组中第K个最大元素
 */
public class FindKthLargest {
    
    public static void main(String[] args) {
        int[] numbers = new int[]{1, 4, 5, 2, 7, 3, 6, 8, 10, 9, -1};
        for(int i : numbers){
            System.out.print(i + ", ");
        }
        System.out.println();
        System.out.println(findKthEnum(numbers, 2));
    }
    
    public static int findKthEnum(int[] numbers, int k){
        return querySelect(numbers, 0, numbers.length -1, numbers.length - k);
    }

    /**
     * 寻找第index大小位置
     * @param numbers
     * @param start
     * @param end
     * @param index
     * @return
     */
    public static int querySelect(int[] numbers, int start, int end, int index){
        int q = findIndex(numbers, start, end);
        if(q == index){
            return numbers[q];
        }else {
            return q > index ? querySelect(numbers, start, q -1, index) : querySelect(numbers, q + 1, end, index);
        }
    }
    //一次循环交换
    public static int findIndex(int[] numbers, int start, int end){
        int le = start;
        int ri = end;
        if(start >= end){
            return le;
        }
        while(le != ri){
            if(numbers[ri] >= numbers[start]){
                ri --;
                continue;
            }
            if(numbers[le] <= numbers[start]){
                le ++;
                continue;
            }
            //交换元素
            if(numbers[le] > numbers[start] && numbers[ri] < numbers[start]){
                swap(numbers, le, ri);
            }
        }
        //基数
        swap(numbers, start, le);
        return le;
    }
    
    public static void swap(int[] numbers, int i, int j){
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
    
    
    public static void quickSort(int[] numbers, int start, int end, int index){
        if(start >= end){
            return;
        }
        int le = start;
        int ri = end;
        while(le != ri){
            if(numbers[ri] >= numbers[start]){
                ri --;
                continue;
            }
            if(numbers[le] <= numbers[start]){
                le ++;
                continue;
            }
            //交换元素
            if(numbers[le] > numbers[start] && numbers[ri] < numbers[start]){
                swap(numbers, le, ri);
            }
        }
        
        //基数
        swap(numbers, start, le);
        //左边
        quickSort(numbers, start, le -1, index);
        //右边
        quickSort(numbers, le + 1, end, index);
    }

    /**
     * 多次循环
     * @param a
     * @param left
     * @param right
     */
    public static void quicksort(int[] a, int left, int right) {
        int i, j, t, temp;
        if(left > right)
            return;
        temp = a[left]; //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要，要先从右边开始找
            while(a[j] >= temp && i < j)
                j--;
            while(a[i] <= temp && i < j)//再找右边的
                i++;
            if(i < j)//交换两个数在数组中的位置
            {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(a, left, i-1);//继续处理左边的，这里是一个递归的过程
        quicksort(a,i+1, right);//继续处理右边的 ，这里是一个递归的过程
    }
}
